#include "hashtable.hpp"
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
#include <string>

using namespace std::chrono;
using namespace STL;

// 生成随机字符串
std::string rand_key(std::mt19937& rng, int len = 8) {
    static const char charset[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    std::uniform_int_distribution<> dist(0, sizeof(charset) - 2);
    std::string s(len, 0);
    for (char& c : s) c = charset[dist(rng)];
    return s;
}

// KSHash 专用测试函数
void test_kshash_performance() {
    std::cout << "\n=== KSHash (开放定址法) 性能测试 ===\n";
    
    std::random_device rd;
    std::mt19937 rng(rd());
    std::uniform_int_distribution<int> key_dist(0, 1000000);
    
    KSHash::HashTable<int, std::string> ht;
    
    // 插入性能测试
    auto start = high_resolution_clock::now();
    
    int insert_count = 10000;
    for (int i = 0; i < insert_count; ++i) {
        int key = key_dist(rng);
        ht.Insert({key, "value_" + std::to_string(key)});
    }
    
    auto end = high_resolution_clock::now();
    auto insert_time = duration_cast<milliseconds>(end - start);
    
    std::cout << "插入 " << insert_count << " 个随机元素耗时: " << insert_time.count() << " ms\n";
    std::cout << "元素数量: " << ht.size() << "\n";
    
    // 查找性能测试
    start = high_resolution_clock::now();
    
    int find_count = 1000;
    int found_count = 0;
    for (int i = 0; i < find_count; ++i) {
        int key = key_dist(rng);
        if (ht.Find(key) != nullptr) {  // KSHash 返回指针
            found_count++;
        }
    }
    
    end = high_resolution_clock::now();
    auto find_time = duration_cast<microseconds>(end - start);
    
    std::cout << "查找 " << find_count << " 次耗时: " << find_time.count() << " us\n";
    std::cout << "命中次数: " << found_count << "\n";
    
    // 字符串键测试
    std::cout << "\n--- KSHash 字符串键测试 ---\n";
    KSHash::HashTable<std::string, int> ht_str;
    
    start = high_resolution_clock::now();
    
    int str_insert_count = 3000;
    for (int i = 0; i < str_insert_count; ++i) {
        std::string key = rand_key(rng, 10);
        ht_str.Insert({key, i});
    }
    
    end = high_resolution_clock::now();
    auto str_insert_time = duration_cast<milliseconds>(end - start);
    
    std::cout << "插入 " << str_insert_count << " 个字符串键耗时: " << str_insert_time.count() << " ms\n";
    std::cout << "元素数量: " << ht_str.size() << "\n";
    
    // 删除性能测试
    std::cout << "\n--- KSHash 删除性能测试 ---\n";
    std::cout << "删除前元素数量: " << ht.size() << "\n";
    
    start = high_resolution_clock::now();
    
    int delete_count = 1000;
    int deleted_count = 0;
    for (int i = 0; i < delete_count; ++i) {
        if (ht.Erase(i)) {
            deleted_count++;
        }
    }
    
    end = high_resolution_clock::now();
    auto delete_time = duration_cast<milliseconds>(end - start);
    
    std::cout << "删除 " << deleted_count << " 个元素耗时: " << delete_time.count() << " ms\n";
    std::cout << "删除后元素数量: " << ht.size() << "\n";
}

// BSHash 专用测试函数
void test_bshash_performance() {
    std::cout << "\n=== BSHash (链地址法) 性能测试 ===\n";
    
    std::random_device rd;
    std::mt19937 rng(rd());
    std::uniform_int_distribution<int> key_dist(0, 1000000);
    
    BSHash::HashTable<int, std::string> ht;
    
    // 插入性能测试
    auto start = high_resolution_clock::now();
    
    int insert_count = 10000;
    for (int i = 0; i < insert_count; ++i) {
        int key = key_dist(rng);
        ht.Insert({key, "value_" + std::to_string(key)});
    }
    
    auto end = high_resolution_clock::now();
    auto insert_time = duration_cast<milliseconds>(end - start);
    
    std::cout << "插入 " << insert_count << " 个随机元素耗时: " << insert_time.count() << " ms\n";
    std::cout << "最终表大小: " << ht.TableSize() << "\n";
    std::cout << "元素数量: " << ht.Size() << "\n";
    std::cout << "负载因子: " << (double)ht.Size() / ht.TableSize() << "\n";
    
    // 查找性能测试
    start = high_resolution_clock::now();
    
    int find_count = 1000;
    int found_count = 0;
    for (int i = 0; i < find_count; ++i) {
        int key = key_dist(rng);
        if (ht.Find(key).second) {  // BSHash 返回 pair<iterator, bool>
            found_count++;
        }
    }
    
    end = high_resolution_clock::now();
    auto find_time = duration_cast<microseconds>(end - start);
    
    std::cout << "查找 " << find_count << " 次耗时: " << find_time.count() << " us\n";
    std::cout << "命中次数: " << found_count << "\n";
    
    // 字符串键测试
    std::cout << "\n--- BSHash 字符串键测试 ---\n";
    BSHash::HashTable<std::string, int> ht_str;
    
    start = high_resolution_clock::now();
    
    int str_insert_count = 3000;
    for (int i = 0; i < str_insert_count; ++i) {
        std::string key = rand_key(rng, 10);
        ht_str.Insert({key, i});
    }
    
    end = high_resolution_clock::now();
    auto str_insert_time = duration_cast<milliseconds>(end - start);
    
    std::cout << "插入 " << str_insert_count << " 个字符串键耗时: " << str_insert_time.count() << " ms\n";
    std::cout << "最终表大小: " << ht_str.TableSize() << "\n";
    std::cout << "元素数量: " << ht_str.Size() << "\n";
    
    // 删除性能测试
    std::cout << "\n--- BSHash 删除性能测试 ---\n";
    std::cout << "删除前元素数量: " << ht.Size() << "\n";
    
    start = high_resolution_clock::now();
    
    int delete_count = 1000;
    int deleted_count = 0;
    for (int i = 0; i < delete_count; ++i) {
        if (ht.Erase(i)) {
            deleted_count++;
        }
    }
    
    end = high_resolution_clock::now();
    auto delete_time = duration_cast<milliseconds>(end - start);
    
    std::cout << "删除 " << deleted_count << " 个元素耗时: " << delete_time.count() << " ms\n";
    std::cout << "删除后元素数量: " << ht.Size() << "\n";
}

// 冲突测试
void test_collision_performance() {
    std::cout << "\n=== 冲突处理性能对比 ===\n";
    
    // KSHash 冲突测试
    std::cout << "\n--- KSHash 冲突测试 ---\n";
    KSHash::HashTable<int, std::string> ht_ks;
    
    std::vector<int> conflict_keys = {0, 53, 106, 159, 212, 265, 318};
    
    auto start = high_resolution_clock::now();
    for (int key : conflict_keys) {
        ht_ks.Insert({key, "conflict_" + std::to_string(key)});
    }
    auto end = high_resolution_clock::now();
    auto ks_insert_time = duration_cast<microseconds>(end - start);
    
    start = high_resolution_clock::now();
    int ks_found = 0;
    for (int key : conflict_keys) {
        if (ht_ks.Find(key) != nullptr) {
            ks_found++;
        }
    }
    end = high_resolution_clock::now();
    auto ks_find_time = duration_cast<microseconds>(end - start);
    
    std::cout << "KSHash 插入冲突键耗时: " << ks_insert_time.count() << " us\n";
    std::cout << "KSHash 查找冲突键耗时: " << ks_find_time.count() << " us\n";
    std::cout << "KSHash 成功找到: " << ks_found << " 个键\n";
    
    // BSHash 冲突测试
    std::cout << "\n--- BSHash 冲突测试 ---\n";
    BSHash::HashTable<int, std::string> ht_bs(53);  // 小表制造冲突
    
    start = high_resolution_clock::now();
    for (int key : conflict_keys) {
        ht_bs.Insert({key, "conflict_" + std::to_string(key)});
    }
    end = high_resolution_clock::now();
    auto bs_insert_time = duration_cast<microseconds>(end - start);
    
    start = high_resolution_clock::now();
    int bs_found = 0;
    for (int key : conflict_keys) {
        if (ht_bs.Find(key).second) {
            bs_found++;
        }
    }
    end = high_resolution_clock::now();
    auto bs_find_time = duration_cast<microseconds>(end - start);
    
    std::cout << "BSHash 插入冲突键耗时: " << bs_insert_time.count() << " us\n";
    std::cout << "BSHash 查找冲突键耗时: " << bs_find_time.count() << " us\n";
    std::cout << "BSHash 成功找到: " << bs_found << " 个键\n";
}

// 基础功能验证
void basic_function_test() {
    std::cout << "\n=== 基础功能验证 ===\n";
    
    // 测试 KSHash
    {
        std::cout << "\n--- KSHash 基础功能测试 ---\n";
        KSHash::HashTable<int, std::string> ht;
        
        ht.Insert({1, "one"});
        ht.Insert({2, "two"});
        ht.Insert({3, "three"});
        
        auto found = ht.Find(2);
        if (found != nullptr) {
            std::cout << "KSHash 找到 key=2: " << found->_kv.second << "\n";
        }
        
        ht.Erase(2);
        if (ht.Find(2) == nullptr) {
            std::cout << "KSHash 删除成功\n";
        }
        
        std::cout << "KSHash 元素数量: " << ht.size() << "\n";
    }
    
    // 测试 BSHash
    {
        std::cout << "\n--- BSHash 基础功能测试 ---\n";
        BSHash::HashTable<int, std::string> ht;
        
        ht.Insert({1, "one"});
        ht.Insert({2, "two"});
        ht.Insert({3, "three"});
        
        auto found = ht.Find(2);
        if (found.second) {
            std::cout << "BSHash 找到 key=2: " << found.first->second << "\n";
        }
        
        ht.Erase(2);
        if (!ht.Find(2).second) {
            std::cout << "BSHash 删除成功\n";
        }
        
        std::cout << "BSHash 元素数量: " << ht.Size() << "\n";
    }
}

int main() {
    std::cout << "========================================\n";
    std::cout << "         哈希表性能对比测试\n";
    std::cout << "========================================\n";
    
    // 先运行基础功能测试
    basic_function_test();
    
    // 分别测试两种哈希表
    test_kshash_performance();
    test_bshash_performance();
    
    // 冲突测试对比
    test_collision_performance();
    
    std::cout << "\n========================================\n";
    std::cout << "             测试完成\n";
    std::cout << "========================================\n";
    
    return 0;
}